home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / agrep / mgrep.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  8KB  |  324 lines

  1. /* Copyright (c) 1991 Sun Wu and Udi Manber.  All Rights Reserved. */
  2. /* multipattern matcher */
  3. #include <stdio.h>
  4. #include <ctype.h>
  5. #define MAXPAT  256
  6. #define MAXLINE 1024
  7. #define MAXSYM  256
  8. #define MAXMEMBER1 4096
  9. #define MAXPATFILE 260000
  10. #define BLOCKSIZE  8192
  11. #define MAXHASH    8192
  12. #define mm        8191
  13. #define max_num    30000  
  14. #define W_DELIM       128
  15. #define L_DELIM    10 
  16.  
  17. extern COUNT, FNAME, SILENT, FILENAMEONLY, num_of_matched;
  18. extern INVERSE;
  19. extern WORDBOUND, WHOLELINE, NOUPPER;
  20. extern unsigned char  CurrentFileName[], Progname[]; 
  21. extern total_line;
  22.  
  23. int LONG  = 0;
  24. int SHORT = 0;
  25. int p_size=0;
  26. unsigned char SHIFT1[MAXMEMBER1];
  27. unsigned char tr[MAXSYM];
  28. unsigned char tr1[MAXSYM];
  29. struct pat_list {
  30.     int  index;
  31.     struct pat_list *next;
  32. } *HASH[MAXHASH];
  33. struct pat_list  *pt, *qt;
  34. unsigned char buf[MAXPATFILE+BLOCKSIZE];
  35. unsigned char pat_spool[MAXPATFILE+2*max_num+MAXPAT];
  36. unsigned char *patt[max_num];
  37. unsigned char pat_len[max_num];
  38.  
  39.  
  40. prepf(fp)
  41. int fp;
  42. {
  43.     int length=0, i, p=1, pdx=0, num_pat;
  44.     unsigned char *pat_ptr=pat_spool, temp[10];
  45.     unsigned Mask = 15;
  46.     int num_read;
  47.  
  48.     while((num_read = read(fp, buf+length, BLOCKSIZE)) > 0) {
  49.     length = length + num_read;
  50.     if(length > MAXPATFILE) {
  51.         fprintf(stderr, "%s: maximum pattern file size is %d\n", Progname, MAXPATFILE);
  52.         exit(2);
  53.     }
  54.     }
  55.     buf[length] = '\n';
  56.     i = 0; p=1;
  57.     while(i<length) {
  58.     patt[p] = pat_ptr;
  59.     if(WORDBOUND) *pat_ptr++ = W_DELIM;
  60.     if(WHOLELINE) *pat_ptr++ = L_DELIM;
  61.     while((*pat_ptr = buf[i++]) != '\n') pat_ptr++;
  62.     if(WORDBOUND) *pat_ptr++ = W_DELIM;
  63.     if(WHOLELINE) *pat_ptr++ = L_DELIM;           /* Can't be both on */
  64.     *pat_ptr++ = 0;
  65.     p++;  
  66.     }
  67.     if(p>max_num) {
  68.     fprintf(stderr, "%s: maximum number of patterns is %d\n", Progname, max_num); 
  69.     exit(2);
  70.     }
  71.     for(i=1; i<20; i++) *pat_ptr = i;  /* boundary safety zone */
  72.     for(i=0; i< MAXSYM; i++) tr[i] = i;
  73.     if(NOUPPER) {
  74.     for(i='A'; i<= 'Z'; i++) tr[i] = i + 'a' - 'A';
  75.     }
  76.     if(WORDBOUND) {
  77.     for(i=0; i<128; i++) if(!isalnum(i)) tr[i] = W_DELIM;
  78.     }
  79.     for(i=0; i< MAXSYM; i++) tr1[i] = tr[i]&Mask;
  80.     num_pat = p-1;
  81.     p_size = MAXPAT;
  82.     for(i=1 ; i <= num_pat; i++) {
  83.     p = strlen(patt[i]);
  84.     pat_len[i] = p;
  85.     if(p!=0 && p < p_size) p_size = p;
  86.     }
  87.     if(p_size == 0) {
  88.     fprintf(stderr, "%s: the pattern file is empty\n");
  89.     exit(2);
  90.     }
  91.     if(length > 400 && p_size > 2) LONG = 1;
  92.     if(p_size == 1) SHORT = 1;
  93.     for(i=0; i<MAXMEMBER1; i++) SHIFT1[i] = p_size - 2;
  94.     for(i=0; i<MAXHASH; i++) {
  95.     HASH[i] = 0;
  96.     }
  97.     for(i=1; i<= num_pat; i++) f_prep(i, patt[i]);
  98. }
  99.  
  100.  
  101. mgrep(fd)
  102. int fd;
  103.     register char r_newline = '\n';
  104.     unsigned char text[2*BLOCKSIZE+MAXLINE]; 
  105.     register int buf_end, num_read, i=0, j, start, end, residue = 0;
  106.  
  107.     text[MAXLINE-1] = '\n';  /* initial case */
  108.     start = MAXLINE-1;
  109.  
  110.     while( (num_read = read(fd, text+MAXLINE, BLOCKSIZE)) > 0) 
  111.     {
  112.        if(INVERSE && COUNT) countline(text+MAXLINE, num_read);
  113.        buf_end = end = MAXLINE + num_read -1 ;
  114.        while(text[end]  != r_newline && end > MAXLINE) end--;
  115.        residue = buf_end - end  + 1 ;
  116.        text[start-1] = r_newline;
  117.        if(SHORT) m_short(text, start, end);
  118.        else      monkey1(text, start, end);
  119.        if(FILENAMEONLY && num_of_matched) {
  120.         printf("%s\n", CurrentFileName);
  121.         return;
  122.        }
  123.        start = MAXLINE - residue;
  124.        if(start < 0) {
  125.             start = 1; 
  126.        }
  127.        strncpy(text+start, text+end, residue);
  128.     } /* end of while(num_read = ... */
  129.     text[MAXLINE] = '\n';
  130.     text[start-1] = '\n';
  131.     if(residue > 1) {
  132.         if(SHORT) m_short(text, start, end);
  133.         else      monkey1(text, start, end);
  134.     }
  135.     return;
  136. } /* end mgrep */
  137.  
  138. countline(text, len)
  139. unsigned char *text; int len;
  140. {
  141. int i;
  142.     for (i=0; i<len; i++) if(text[i] == '\n') total_line++;
  143. }
  144.  
  145.  
  146. monkey1( text, start, end  ) 
  147. int start, end; register unsigned char *text;
  148. {
  149. register unsigned char *textend;
  150. register unsigned hash, i;
  151. register unsigned char shift; 
  152. register int  m1, j, Long=LONG; 
  153. int pat_index, m=p_size; 
  154. int MATCHED=0;
  155. register unsigned char *qx;
  156. register struct pat_list *p;
  157. unsigned char *lastout;
  158. int OUT=0;
  159.  
  160. textend = text + end;
  161. m1 = m - 1;
  162. lastout = text+start+1;
  163. text = text + start + m1 ;
  164. while (text <= textend) {
  165.     hash=tr1[*text];
  166.     hash=(hash<<4)+(tr1[*(text-1)]);
  167.     if(Long) hash=(hash<<4)+(tr1[*(text-2)]);
  168.     shift = SHIFT1[hash];
  169.     if(shift == 0) {
  170.         hash=0;
  171.         for(i=0;i<=m1;i++)  {
  172.             hash=(hash<<4)+(tr1[*(text-i)]);
  173.         }
  174.         hash=hash&mm;
  175.         p = HASH[hash];
  176.         while(p != 0) {
  177.             pat_index = p->index;
  178.             p = p->next;
  179.             qx = text-m1;
  180.             j = 0;
  181.             while(tr[patt[pat_index][j]] == tr[*(qx++)]) j++;
  182.                 if (j > m1 ) { 
  183.                if(pat_len[pat_index] <= j) {
  184.                 if(text > textend) return;
  185.                         num_of_matched++;
  186.                         if(FILENAMEONLY || SILENT)  return;
  187.                 MATCHED=1;
  188.                     if(COUNT) {
  189.                       while (*text != '\n') text++;
  190.                 }
  191.                 else {
  192.                     if(!INVERSE) {
  193.                       if(FNAME) printf("%s: ",CurrentFileName);
  194.                                   while(*(--text) != '\n');
  195.                                   while(*(++text) != '\n') putchar(*text);
  196.                       printf("\n");
  197.                     }
  198.                     else {
  199.                       if(FNAME) printf("%s: ",CurrentFileName);
  200.                                   while(*(--text) != '\n');
  201.                     if(lastout < text) OUT=1;
  202.                     while(lastout < text) putchar(*lastout++);
  203.                     if(OUT) {
  204.                         putchar('\n');
  205.                         OUT=0;
  206.                     }
  207.                                   while(*(++text) != '\n');
  208.                     lastout=text+1;
  209.                     }
  210.                 }
  211. /*
  212.                 else {
  213.                       if(FNAME) printf("%s: ",CurrentFileName);
  214.                                   while(*(--text) != '\n');
  215.                                   while(*(++text) != '\n') putchar(*text);
  216.                       printf("\n");
  217.                 }
  218. */
  219.                }
  220.                     }
  221.             if(MATCHED) break;
  222.         }
  223.         if(!MATCHED) shift = 1;
  224.         else {
  225.             MATCHED = 0;
  226.             shift = m1;
  227.         }
  228.         }
  229.     text = text + shift;
  230.   }
  231.   if(INVERSE && !COUNT) while(lastout <= textend) putchar(*lastout++);
  232. }
  233.  
  234. m_short( text, start, end  ) 
  235. int start, end; register unsigned char *text;
  236. {
  237. register unsigned char *textend;
  238. register unsigned i; 
  239. register int  j; 
  240. register struct pat_list *p, *q;
  241. register int pat_index; 
  242. int MATCHED=0;
  243. int OUT=0;
  244. unsigned char *lastout;
  245. unsigned char *qx;
  246.  
  247. textend = text + end;
  248. lastout = text + start + 1;
  249. text = text + start - 1 ;
  250. while (++text <= textend) {
  251.         p = HASH[*text];
  252.         while(p != 0) {
  253.             pat_index = p->index;
  254.             p = p->next;
  255.             qx = text;
  256.             j = 0;
  257.             while(tr[patt[pat_index][j]] == tr[*(qx++)]) j++;
  258.             if(pat_len[pat_index] <= j) {
  259.                 if(text >= textend) return;
  260.                         num_of_matched++;
  261.                         if(FILENAMEONLY || SILENT)  return;
  262.                     if(COUNT) {
  263.                       while (*text != '\n') text++;
  264.                 }
  265.                 else {
  266.                       if(FNAME) printf("%s: ",CurrentFileName);
  267.                     if(!INVERSE) {
  268.                                   while(*(--text) != '\n');
  269.                                   while(*(++text) != '\n') putchar(*text);
  270.                       printf("\n");
  271.                     MATCHED = 1;
  272.                     }
  273.                     else {
  274.                                   while(*(--text) != '\n');
  275.                     if(lastout < text) OUT=1;
  276.                     while(lastout < text) putchar(*lastout++);
  277.                     if(OUT) {
  278.                         putchar('\n');
  279.                         OUT=0;
  280.                     }
  281.                                   while(*(++text) != '\n');
  282.                     lastout=text+1;
  283.                     MATCHED = 1;
  284.                     }
  285.                 }
  286.                     }
  287.             if(MATCHED) break;
  288.         }
  289.         MATCHED = 0;
  290.   } /* while */
  291.   if(INVERSE && !COUNT) while(lastout <= textend) putchar(*lastout++);
  292. }
  293.  
  294. f_prep(pat_index, Pattern)
  295. unsigned char *Pattern ; int pat_index;
  296. {
  297. int i, j, m;
  298. register unsigned hash, Mask=15;
  299.     m = p_size;
  300.     for (i = m-1; i>=(1+LONG); i--) {
  301.         hash = (Pattern[i] & Mask);
  302.         hash = (hash << 4) + (Pattern[i-1]& Mask);
  303.         if(LONG) hash = (hash << 4) + (Pattern[i-2] & Mask);
  304.         if(SHIFT1[hash] >= m-1-i) SHIFT1[hash] = m-1-i;
  305.     }
  306.     if(SHORT) Mask = 255;  /* 011111111 */
  307.     hash = 0;
  308.     for(i = m-1; i>=0; i--)  {
  309.         hash = (hash << 4) + (tr[Pattern[i]]&Mask);
  310.     }
  311. /*
  312.     if(INVERSE) hash = Pattern[1];
  313. */
  314.     hash=hash&mm;
  315.     qt = (struct pat_list *) malloc(sizeof(struct pat_list));
  316.     qt->index = pat_index;
  317.     pt = HASH[hash];
  318.     qt->next = pt;
  319.     HASH[hash] = qt;
  320. }
  321.  
  322.  
  323.